๐Ÿงฉ Virtual Memory

@Seongukbaek Posted August 20, 2022 ยท Updated August 20, 2022 ยท 9 min read

๊ฐ€์ƒ ๋ฉ”๋ชจ๋ฆฌ๋Š” ๋ฌผ๋ฆฌ ๋ฉ”๋ชจ๋ฆฌ ํฌ๊ธฐ์˜ ํ•œ๊ณ„๋ฅผ ๊ทน๋ณตํ•˜๊ธฐ ์œ„ํ•ด ๋‚˜์˜จ ๊ธฐ์ˆ ์ด๋‹ค. ๋”ฐ๋ผ์„œ, ๋ฌผ๋ฆฌ ๋ฉ”๋ชจ๋ฆฌ๋ณด๋‹ค ํฐ ํ”„๋กœ์„ธ์Šค๋ฅผ ์ˆ˜ํ–‰ํ•˜๊ธฐ ์œ„ํ•ด ๊ฐ€์ƒ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.

๐Ÿงท Demanding Paging

ํ˜„์žฌ ํ•„์š”ํ•œ(์š”๊ตฌ๋˜๋Š”) ํŽ˜์ด์ง€๋งŒ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ฆฌ๋Š” ๊ฒƒ์„ ๋งํ•œ๋‹ค.

  • ์ ‘๊ทผ๋˜์ง€ ์•Š๋Š” ํŽ˜์ด์ง€๋Š” ์ ˆ๋Œ€ ๋กœ๋“œ๋˜์ง€ ์•Š๋Š”๋‹ค.
  • swap in์ด ๋ฐœ์ƒํ•  ๋•Œ, pager๊ฐ€ ์–ด๋–ค page๊ฐ€ ์‚ฌ์šฉ๋  ๊ฒƒ์ธ์ง€๋ฅผ ์ถ”์ธกํ•˜์—ฌ ๋กœ๋“œํ•œ๋‹ค.

    • ๋กœ๋“œ๋œ ํŽ˜์ด์ง€์™€ ๊ทธ๋ ‡์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ valid-invalid bit ๋กœ ๊ตฌ๋ถ„ํ•œ๋‹ค.

๐Ÿงท Page Fault

์ด๋Š” CPU๊ฐ€ ์š”๊ตฌํ•˜๋Š” ํŽ˜์ด์ง€๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์— ๋กœ๋“œ๋˜์–ด ์žˆ์ง€ ์•Š์€ ๊ฒฝ์šฐ๋กœ, ์œ„์—์„œ ์–ธ๊ธ‰ํ•œ valid-invalid bit ์˜ ๊ฐ’์ด i ์ธ ๊ฒฝ์šฐ๋‹ค.

์•„๋ž˜๋Š” ์ด๋ฅผ ์ฒ˜๋ฆฌํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.

  1. CPU๊ฐ€ page table์—์„œ ์‚ฌ์šฉํ•  ํŽ˜์ด์ง€์— ์ ‘๊ทผํ•œ๋‹ค.
  2. ๋ฉ”๋ชจ๋ฆฌ์— ๋กœ๋“œ๋˜์ง€ ์•Š์€ ์ƒํƒœ๋ผ๋ฉด, interrupt๋ฅผ ๋ฐœ์ƒ์‹œํ‚จ๋‹ค.
  3. Disk์—์„œ ํŽ˜์ด์ง€๋ฅผ ์ฐพ๋Š”๋‹ค.
  4. ์ด๋ฅผ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ ค Frameํ™”ํ•œ๋‹ค.
  5. page table์„ ๊ฐฑ์‹ ํ•˜๊ณ , CPU์—๊ฒŒ ๋‹ค์‹œ ์ˆ˜ํ–‰ํ•˜๋ผ๊ณ  ๋ช…๋ นํ•œ๋‹ค.

๐Ÿชš Pure Demanding Paging

ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ตœ์ดˆ๋กœ ์‹คํ–‰๋  ๋•Œ ์–ด๋–ค ํŽ˜์ด์ง€๊ฐ€ ํ•„์š”ํ•œ์ง€ ์•Œ ์ˆ˜ ์—†์–ด, ์•„๋ฌด ํŽ˜์ด์ง€๋„ ์˜ฌ๋ฆฌ์ง€ ์•Š๋Š”๋‹ค.

  • ๋”ฐ๋ผ์„œ ํ”„๋กœ๊ทธ๋žจ ์‹คํ–‰๊ณผ ๋™์‹œ์— Page fault๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค.
  • ์ฆ‰, ์ˆœ์ˆ˜ํ•˜๊ฒŒ ํ•„์š”ํ•œ ํŽ˜์ด์ง€๋งŒ ์˜ฌ๋ฆฌ๋Š” ๊ฒƒ์„ Pure Demanding Paging์ด๋ผ๊ณ  ํ•œ๋‹ค.

๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ตœ๋Œ€ํ•œ ํšจ์œจ์ ์œผ๋กœ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ์žฅ์ ์ด ์žˆ์ง€๋งŒ, ์‹œ์ž‘๋ถ€ํ„ฐ Page fault๊ฐ€ ๋ฐœ์ƒํ•ด ์†๋„๋ฉด์—์„œ๋Š” ๋А๋ฆฌ๋‹ค๋Š” ๋‹จ์ ์ด ์žˆ๋‹ค.

๐Ÿชš Prepaging

Pure Demanding Paging๊ณผ๋Š” ๋ฐ˜๋Œ€๋˜๋Š” ๊ฐœ๋…์œผ๋กœ, ํ”„๋กœ๊ทธ๋žจ ์‹คํ–‰ ์‹œ ํ•„์š”ํ•  ๊ฒƒ์ด๋ผ ํŒ๋‹จ๋˜๋Š” ํŽ˜์ด์ง€๋ฅผ ๋ฏธ๋ฆฌ ์˜ฌ๋ฆฌ๋Š” ๊ฒƒ์ด๋‹ค.

Page fault๊ฐ€ ๋ฐœ์ƒํ•  ํ™•๋ฅ ์ด ์ ์–ด ์†๋„๋ฉด์—์„œ๋Š” ๋น ๋ฅด์ง€๋งŒ, ๋ฏธ๋ฆฌ ์˜ฌ๋ผ๊ฐ„ ํŽ˜์ด์ง€๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ๋‚ญ๋น„๋œ๋‹ค.

๐Ÿชš Swapping vs. Demanding Paging

๋‘˜ ๋‹ค ๋ฉ”๋ชจ๋ฆฌ์™€ backing store ์‚ฌ์ด๋ฅผ ์˜ค๊ณ  ๊ฐ€๋Š” ๊ธฐ๋Šฅ์„ ์ˆ˜ํ–‰ํ•˜์ง€๋งŒ, Swapping์€ ํ”„๋กœ์„ธ์Šค ๋‹จ์œ„๋กœ ์ด๋™ํ•˜๊ณ , Demanding Paging์€ ํŽ˜์ด์ง€ ๋‹จ์œ„๋กœ ์ด๋™ํ•œ๋‹ค๋Š” ์ฐจ์ด๊ฐ€ ์žˆ๋‹ค.


๐Ÿงท Page Replacement

Demanding Paging์€ ์š”๊ตฌ๋˜๋Š” ํŽ˜์ด์ง€๋งŒ backing store์—์„œ ๊ฐ€์ ธ์˜จ๋‹ค. ํ•˜์ง€๋งŒ ํ”„๋กœ๊ทธ๋žจ๋“ค์ด ๊ณ„์† ์‹คํ–‰๋˜๋ฉด์„œ, ์š”๊ตฌ๋˜๋Š” ํŽ˜์ด์ง€๋Š” ๋Š˜์–ด๋‚˜๊ณ  ๋ฉ”๋ชจ๋ฆฌ๋Š” ์œ ํ•œํ•˜๊ธฐ์— ์–ธ์  ๊ฐ€๋Š” ๊ฐ€๋“ ์ฐจ๊ฒŒ ๋˜์–ด ๋” ์ด์ƒ ์ƒˆ๋กœ์šด ํŽ˜์ด์ง€๋ฅผ ๋‹ด์„ ์ˆ˜ ์—†๊ฒŒ ๋  ๊ฒƒ์ด๋‹ค.

  • ๊ทธ๋ ‡๋‹ค๋ฉด, ์ด๋ฏธ ์žˆ๋Š” ํŽ˜์ด์ง€ ์ค‘ ํ•˜๋‚˜๋ฅผ ๋‹ค์‹œ backing store๋กœ ๋‚ด๋ณด๋‚ด๊ณ , ์ƒˆ๋กœ์šด ํŽ˜์ด์ง€๋ฅผ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ ค์•ผ ํ•˜๋Š”๋ฐ, ์ด๋ฅผ Page Replacement๋ผ ํ•œ๋‹ค.
  • backing store๋กœ ๋‚ด๋ณด๋‚ด๋Š” ๊ฒƒ์„ page-out, ๊ทธ ๋ฐ˜๋Œ€๋ฅผ page-in์ด๋ผ ํ•œ๋‹ค.
  • ๊ทธ๋ฆฌ๊ณ  page-out๋œ ํŽ˜์ด์ง€๋ฅผ victim page๋ผ ํ•œ๋‹ค.

๐Ÿชš Victim Page

ํฌ์ƒ์–‘ ํŽ˜์ด์ง€๋Š” ์–ด๋–ค ํŽ˜์ด์ง€๋กœ ์„ ํƒํ•˜๋Š” ๊ฒƒ์ด ์ข‹์„๊นŒ.

์ด๋ฏธ ๋กœ๋“œ๋œ ํŽ˜์ด์ง€ ์ค‘ CPU์— ์ˆ˜์ •(modify)๋˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ๊ณ ๋ฅด๋Š” ๊ฒƒ์ด ํšจ์œจ์ ์ด๋‹ค. ์ด๋Š” ๊ณง ์ฝ๊ธฐ๋งŒ ํ•˜๋Š” ํŽ˜์ด์ง€๋ฅผ ์˜๋ฏธํ•œ๋‹ค. ์ด๋Ÿฌํ•œ ํŽ˜์ด์ง€๋Š” page-out์ด ๋  ๋•Œ backing store์— ์“ฐ๊ธฐ ์—ฐ์‚ฐ์„ ํ•  ํ•„์š”๊ฐ€ ์—†๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.

๊ทธ๋ ‡๋‹ค๋ฉด, ํ•ด๋‹น ํŽ˜์ด์ง€๊ฐ€ ์ˆ˜์ •๋˜์—ˆ๋Š”์ง€ ์•ˆ๋˜์—ˆ๋Š”์ง€๋ฅผ ๊ตฌ๋ถ„ํ•  ์ •๋ณด๊ฐ€ ํ•„์š”ํ•œ๋ฐ, ์ด๋•Œ modify bit = dirty bit ๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค.

์œ„ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์ˆ˜์ •๋˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ๋‚˜ํƒ€๋‚ด๊ณ  ์ด ์ค‘ ์„ ํƒํ•œ๋‹ค.

  • ์ด๋•Œ, ์—ฌ๋Ÿฌ ๊ฐœ์˜ ์ˆ˜์ •๋˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๊ฐ€ ์žˆ๋‹ค๋ฉด ์–ด๋–ค ํŽ˜์ด์ง€๋ฅผ ๊ณจ๋ผ์•ผ ํ• ๊นŒ

๐Ÿชš Page Replacement - FIFO

๊ฐ€์žฅ ๋จผ์ € ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ์˜จ, ์ˆ˜์ •๋˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ํฌ์ƒ์–‘ ํŽ˜์ด์ง€๋กœ ์„ ํƒํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค.

  • ์ตœ์ ์˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์•„๋‹ˆ์ง€๋งŒ, ์ •ํ™•์„ฑ์—๋Š” ์˜ํ–ฅ์„ ๋ฏธ์น˜์ง€ ์•Š๋Š”๋‹ค.
  • ์ด์ „์— page-outํ•œ ํŽ˜์ด์ง€๋ฅผ ๊ทธ ๋‹ค์Œ ๋ฐ”๋กœ page-inํ•˜๋ ค ํ•œ๋‹ค๋ฉด ๋‹ค์‹œ page fault๊ฐ€ ๋ฐœ์ƒํ•ด ๋น„ํšจ์œจ์ ์ด๋‹ค.

Belady's Anomaly

  • ํ”„๋ ˆ์ž„ ์ˆ˜๊ฐ€ ์ฆ๊ฐ€ํ•˜๋ฉด(= ๋ฉ”๋ชจ๋ฆฌ ์šฉ๋Ÿ‰์ด ์ฆ๊ฐ€ํ•˜๋ฉด) page fault ์ˆ˜๊ฐ€ ์ค„์–ด๋“œ๋Š” ๊ฒƒ์ด ์ด์ƒ์ ์ด๋‹ค.

  • ํ•˜์ง€๋งŒ FIFO๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด, ์œ„์™€ ๊ฐ™์ด ํŠน์ • ์ง€์ ์—์„œ ํ”„๋ ˆ์ž„ ์ˆ˜๊ฐ€ ์ฆ๊ฐ€ํ•ด๋„, page fault ์ˆ˜๊ฐ€ ์˜คํžˆ๋ ค ์ฆ๊ฐ€ํ•˜๋Š” ์ด์ƒ ํ˜„์ƒ์ด ๋ฐœ์ƒํ•œ๋‹ค. ์ด๋ฅผ Belady's Anomaly๋ผ ํ•œ๋‹ค.

๐Ÿชš Page Replacement - Optimal

๋ง๊ทธ๋Œ€๋กœ, ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ, ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉ๋˜์ง€ ์•Š์„ ํŽ˜์ด์ง€๋ฅผ ์„ ํƒํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค.

  • ๋ฏธ๋ฆฌ ๋ฏธ๋ž˜ ์ •๋ณด๋ฅผ ์•ˆ๋‹ค๋Š” ๊ฐ€์ • ํ•˜์—, ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉํ•˜์ง€ ์•Š๋Š” Page๋ฅผ ์„ ํƒํ•˜์—ฌ outํ•œ๋‹ค.
  • ์ด๋ก ์ ์œผ๋กœ๋Š” Page fault ๋ฐœ์ƒ์„ ์ค„์ผ ์ˆ˜ ์žˆ์ง€๋งŒ, ํ˜„์‹ค์ ์œผ๋กœ ๊ตฌํ˜„์ด ๋ถˆ๊ฐ€๋Šฅํ•˜๋‹ค.

๐Ÿชš Page Replacement - LRU

Least Recently Used์˜ ์•ฝ์ž๋กœ, ์ตœ๊ทผ์— ์‚ฌ์šฉ๋˜์ง€ ์•Š์œผ๋ฉด ๋‚˜์ค‘์—๋„ ์‚ฌ์šฉ๋˜์ง€ ์•Š์„ ๊ฒƒ์ด๋ผ๋Š” ๊ฐœ๋…์„ ์‚ฌ์šฉํ•˜๋Š” ๋ฐฉ์‹์ด๋‹ค.

  • ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉํ•˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ํฌ์ƒ์–‘ ํŽ˜์ด์ง€๋กœ ์„ ํƒํ•œ๋‹ค.
  • OPT๋ณด๋‹ค๋Š” Page fault๊ฐ€ ๋งŽ์ด ๋ฐœ์ƒํ•˜์ง€๋งŒ, FIFO๋ณด๋‹ค๋Š” ์ ๊ฒŒ ์ผ์–ด๋‚œ๋‹ค.
  • ๋งŽ์€ ์šด์˜์ฒด์ œ๊ฐ€ ์‚ฌ์šฉํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

๐Ÿชš Page Replacement - LFU

Least Frequently Used์˜ ์•ฝ์ž๋กœ, ์ฐธ์กฐํšŸ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ์ ์€ ํŽ˜์ด์ง€๋ฅผ ๊ต์ฒดํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

  • ๊ต์ฒด ๋Œ€์ƒ์ด ์—ฌ๋Ÿฌ ๊ฐœ๋ผ๋ฉด ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉํ•˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ๊ต์ฒดํ•œ๋‹ค.
  • ํ•˜์ง€๋งŒ ์ฐธ์กฐ๋  ๊ฐ€๋Šฅ์„ฑ์ด ๋งŽ์Œ์—๋„ ๋ถˆ๊ตฌํ•˜๊ณ , ํšŸ์ˆ˜์— ์˜์กดํ•˜๊ธฐ์— ์ตœ๊ทผ์— ์‚ฌ์šฉ๋œ ํ”„๋กœ๊ทธ๋žจ์„ ๊ต์ฒด์‹œํ‚ฌ ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ๋‹ค.

๐Ÿชš Page Replacement - MFU

Most Frequently Used์˜ ์•ฝ์ž๋กœ, LFU์™€ ๋ฐ˜๋Œ€๋กœ ์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋งŽ์€ ํŽ˜์ด์ง€๋ฅผ ๊ต์ฒดํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.


๐Ÿงท Thrashing

๋ฉ”๋ชจ๋ฆฌ ์˜์—ญ์— ์ ‘๊ทผํ•˜๊ฒŒ ๋  ๋•Œ, ๋ฉ”๋ชจ๋ฆฌ์— Page fault์œจ์ด ๋†’์€ ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ์ด๋Š” ์„ฑ๋Šฅ ์ €ํ•˜์˜ ์›์ธ์ด ๋œ๋‹ค.

๐Ÿชš Page-Fault Frequency

๋†’์€ PFF๋Š” ํ”„๋กœ์„ธ์Šค์— ํ”„๋ ˆ์ž„ ์ˆ˜๊ฐ€ ์ถฉ๋ถ„ํžˆ ๋งŽ์ง€ ์•Š์€ ๊ฒฝ์šฐ์— ๋ฐœ์ƒํ•˜๊ณ , ๋‚ฎ์€ PFF๋Š” ํ”„๋กœ์„ธ์Šค์— ํ”„๋ ˆ์ž„ ์ˆ˜๊ฐ€ ๋„ˆ๋ฌด ๋งŽ์€ ๊ฒฝ์šฐ์— ๋ฐœ์ƒํ•œ๋‹ค.

  • ํ”„๋ ˆ์ž„ ์ˆ˜๋ฅผ ๊ด€๋ฆฌํ•จ์œผ๋กœ์จ PFF๋ฅผ ์กฐ์ ˆํ•  ์ˆ˜ ์žˆ๋‹ค.

๐Ÿ“• ์ฐธ๊ณ 

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€